{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #补给马车"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: supplyWagon"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #补给马车"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "远征队即将开启未知的冒险之旅，不过在此之前，将对补给车队进行最后的检查。`supplies[i]` 表示编号为 `i` 的补给马车装载的物资数量。\n",
    "考虑到车队过长容易被野兽偷袭，他们决定将车队的长度变为原来的一半（向下取整），计划为：\n",
    "- 找出车队中 **物资之和最小** 两辆 **相邻** 马车，将它们车辆的物资整合为一辆。若存在多组物资之和相同的马车，则取编号最小的两辆马车进行整合；\n",
    "- 重复上述操作直到车队长度符合要求。\n",
    "\n",
    "请返回车队长度符合要求后，物资的分布情况。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`supplies = [7,3,6,1,8]`\n",
    ">\n",
    ">输出：`[10,15]`\n",
    ">\n",
    ">解释：\n",
    "> 第 1 次合并，符合条件的两辆马车为 6,1，合并后的车队为 [7,3,7,8]；\n",
    "> 第 2 次合并，符合条件的两辆马车为 (7,3) 和 (3,7)，取编号最小的 (7,3)，合并后的车队为 [10,7,8]；\n",
    "> 第 3 次合并，符合条件的两辆马车为 7,8，合并后的车队为 [10,15]；\n",
    ">返回 `[10,15]`\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`supplies = [1,3,1,5]`\n",
    ">\n",
    ">输出：`[5,5]`\n",
    "\n",
    "**解释：**\n",
    "- `2 <= supplies.length <= 1000`\n",
    "- `1 <= supplies[i] <= 1000`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [hqCnmP](https://leetcode.cn/problems/hqCnmP/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [hqCnmP](https://leetcode.cn/problems/hqCnmP/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,3,6,1,8]', '[1,3,1,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        n = len(supplies)\n",
    "        while(len(supplies) > n/2):\n",
    "            Min = supplies[0] + supplies[1]\n",
    "            Min_i = 1\n",
    "            for i in range(2, len(supplies)):\n",
    "                if supplies[i-1] + supplies[i] < Min:\n",
    "                    Min = supplies[i-1] + supplies[i]\n",
    "                    Min_i = i\n",
    "            supplies[Min_i-1] += supplies[Min_i]\n",
    "            del supplies[Min_i]\n",
    "        return supplies\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        n=len(supplies)\n",
    "        k=n-n//2 # 合并的次数\n",
    "        while k:\n",
    "            sm=2000\n",
    "            x=-1\n",
    "            for i in range(1,len(supplies)):\n",
    "            \tif supplies[i-1]+supplies[i]<sm:\n",
    "                    sm=supplies[i-1]+supplies[i]\n",
    "                    x=i\n",
    "        \t\n",
    "            \n",
    "            a=sum(supplies[x-1:x+1])\n",
    "            supplies[x-1]=a\n",
    "            supplies.pop(x)\n",
    "            k-=1\n",
    "            # print(supplies)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        length = len(supplies)\n",
    "        time = length // 2\n",
    "        for i in range(length - time):\n",
    "            min = 2001\n",
    "            index = 0\n",
    "            for i in range(len(supplies) - 1):\n",
    "                temp = supplies[i] + supplies[i + 1]\n",
    "                if min > temp:\n",
    "                    min = temp\n",
    "                    index = i\n",
    "            supplies[index] = min\n",
    "            supplies.pop(index + 1)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        m=len(supplies)//2\n",
    "        while len(supplies)>m:\n",
    "            t=0\n",
    "            for i in range(len(supplies)-1):\n",
    "                if supplies[i]+supplies[i+1]<supplies[t]+supplies[t+1]:\n",
    "                    t=i\n",
    "            supplies[t]+=supplies[t+1]\n",
    "            supplies.pop(t+1)\n",
    "        return supplies\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        length = len(supplies)\n",
    "        while len(supplies) > length // 2:\n",
    "            min_num = float('inf')\n",
    "            min_index = 0\n",
    "            for i in range(len(supplies) - 1):\n",
    "                sup_sum = supplies[i] + supplies[i + 1]\n",
    "                if sup_sum < min_num:\n",
    "                    min_index = i\n",
    "                    min_num = sup_sum\n",
    "            supplies[min_index] += supplies[min_index + 1]\n",
    "            supplies.pop(min_index + 1)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        n = len(supplies)\n",
    "        while len(supplies) > n // 2:\n",
    "            res = 9999999\n",
    "            idx = -1\n",
    "            for i in range(len(supplies)-1):\n",
    "                if res > supplies[i] + supplies[i+1]:\n",
    "                    idx = i\n",
    "                    res = supplies[i] + supplies[i+1]\n",
    "            supplies[idx] = res\n",
    "            supplies.pop(idx+1)\n",
    "        return supplies\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        n=len(supplies)//2\n",
    "        while len(supplies)>n:\n",
    "            k=1\n",
    "            for i in range(1,len(supplies)):\n",
    "                if supplies[i-1]+supplies[i]<supplies[k-1]+supplies[k]:\n",
    "                    k=i\n",
    "            supplies[k-1]+=supplies[k]\n",
    "            supplies.pop(k)\n",
    "        return supplies\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        m = len(supplies) // 2\n",
    "        while len(supplies) > m:\n",
    "            idx = 1\n",
    "            for i in range(1, len(supplies)):\n",
    "                if supplies[i-1] + supplies[i] < supplies[idx - 1] + supplies[idx]:\n",
    "                    idx = i\n",
    "            supplies[idx-1] += supplies[idx]\n",
    "            supplies.pop(idx)\n",
    "        return supplies\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "#         length = int(len(supplies) / 2)\n",
    "#         while len(supplies) > length:\n",
    "#             minsum = supplies[0] + supplies[1]\n",
    "#             order = 0\n",
    "#             for i in range(1, len(supplies) - 1):\n",
    "#                 sum = supplies[i] + supplies[i + 1]\n",
    "#                 if sum < minsum:\n",
    "#                     minsum = sum\n",
    "#                     order = i\n",
    "#             tmp = supplies[:order]\n",
    "#             tmp.append((supplies[order] + supplies[order + 1]))\n",
    "#             supplies = tmp + supplies[order + 2:]\n",
    "#         return supplies\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: list[int]) -> list[int]:\n",
    "        length = int(len(supplies) / 2)\n",
    "        while len(supplies) > length:\n",
    "            minsum = supplies[0] + supplies[1]\n",
    "            order = 0\n",
    "            for i in range(1, len(supplies) - 1):\n",
    "                sum = supplies[i] + supplies[i + 1]\n",
    "                if sum < minsum:\n",
    "                    minsum = sum\n",
    "                    order = i\n",
    "            supplies[order] = supplies[order] + supplies[order + 1]\n",
    "            supplies.pop(order + 1)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        m = len(supplies) // 2\n",
    "        while len(supplies) > m:\n",
    "            cor = 1\n",
    "            for i in range(1, len(supplies)):\n",
    "                temp = supplies[cor - 1] + supplies[cor]\n",
    "                if supplies[i - 1] + supplies[i] < temp:\n",
    "                    cor = i\n",
    "                    temp = supplies[i - 1] + supplies[i]\n",
    "            supplies[cor - 1] = temp\n",
    "            supplies.pop(cor)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, a: List[int]) -> List[int]:\n",
    "        m = len(a) // 2\n",
    "        while len(a) > m:\n",
    "            idx = 1\n",
    "            for i in range(1, len(a)):\n",
    "                if a[i - 1] + a[i] < a[idx - 1] + a[idx]:\n",
    "                    idx = i\n",
    "            a[idx - 1] += a[idx]\n",
    "            a.pop(idx)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, a: List[int]) -> List[int]:\n",
    "        m = len(a) // 2\n",
    "        while len(a) > m:\n",
    "            idx = 1\n",
    "            for i in range(1, len(a)):\n",
    "                if a[i - 1] + a[i] < a[idx - 1] + a[idx]:\n",
    "                    idx = i\n",
    "            a[idx - 1] += a[idx]\n",
    "            a.pop(idx)\n",
    "        return a\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        length = len(supplies)\n",
    "        while len(supplies)>length//2:\n",
    "            min,mark=supplies[0]+supplies[1],0\n",
    "            for i in range(0,len(supplies)-1):\n",
    "                if len(supplies)==3:\n",
    "                    if supplies[0]+supplies[1]>supplies[1]+supplies[2]:\n",
    "                        mark=1\n",
    "                    else:\n",
    "                        mark=0\n",
    "                else:\n",
    "                    if min>supplies[i]+supplies[i+1]:\n",
    "                        min=supplies[i]+supplies[i+1]\n",
    "                        mark=i\n",
    "            supplies[mark+1]=supplies[mark]+supplies[mark+1]\n",
    "            supplies.pop(mark)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        l = len(supplies)//2\n",
    "        while True:\n",
    "            new = []\n",
    "            for i in range(0,len(supplies)-1):\n",
    "                a = supplies[i] + supplies[i+1]\n",
    "                new.append(a)\n",
    "            b = min(new)\n",
    "            index = new.index(b)\n",
    "            supplies[index] = b\n",
    "            del supplies[index+1]\n",
    "            if len(supplies) == l:\n",
    "                break\n",
    "        return supplies\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        length = len(supplies)\n",
    "        while len(supplies)>length//2:\n",
    "            min,mark=supplies[0]+supplies[1],0\n",
    "            for i in range(0,len(supplies)-1):\n",
    "                if len(supplies)==3:\n",
    "                    if supplies[0]+supplies[1]>supplies[1]+supplies[2]:\n",
    "                        mark=1\n",
    "                    else:\n",
    "                        mark=0\n",
    "                else:\n",
    "                    if min>supplies[i]+supplies[i+1]:\n",
    "                        min=supplies[i]+supplies[i+1]\n",
    "                        mark=i\n",
    "            supplies[mark+1]=supplies[mark]+supplies[mark+1]\n",
    "            supplies.pop(mark)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        n = len(supplies)\n",
    "        num_joins = n - n // 2\n",
    "        for i in range(num_joins):\n",
    "            l = n - i\n",
    "            min_sum, min_index = 10000, -1\n",
    "            for j in range(l - 1):\n",
    "                if supplies[j] + supplies[j + 1] < min_sum:\n",
    "                    min_sum = supplies[j] + supplies[j + 1]\n",
    "                    min_index = j\n",
    "            supplies[min_index] += supplies[min_index + 1]\n",
    "            for j in range(min_index + 1, l - 1):\n",
    "                supplies[j] = supplies[j + 1]\n",
    "        return supplies[: n // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        n = len(supplies)\n",
    "        h = n // 2\n",
    "        while n > h:\n",
    "            index, target = 0, supplies[0] + supplies[1]\n",
    "            for i in range(1, n - 1):\n",
    "                s = supplies[i] + supplies[i+1]\n",
    "                if s < target:\n",
    "                    index = i\n",
    "                    target = s\n",
    "            supplies[index] += supplies[index+1]\n",
    "            del supplies[index+1]\n",
    "            n -= 1\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        length = len(supplies)\n",
    "        while len(supplies)>length//2:\n",
    "            min,mark=supplies[0]+supplies[1],0\n",
    "            for i in range(0,len(supplies)-1):\n",
    "                if len(supplies)==3:\n",
    "                    if supplies[0]+supplies[1]>supplies[1]+supplies[2]:\n",
    "                        mark=1\n",
    "                    else:\n",
    "                        mark=0\n",
    "                else:\n",
    "                    if min>supplies[i]+supplies[i+1]:\n",
    "                        min=supplies[i]+supplies[i+1]\n",
    "                        mark=i\n",
    "            supplies[mark+1]=supplies[mark]+supplies[mark+1]\n",
    "            supplies.pop(mark)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        m=len(supplies)//2\n",
    "        while len(supplies)>m:\n",
    "            t=0\n",
    "            for i in range(len(supplies)-1):\n",
    "                if supplies[i]+supplies[i+1]<supplies[t]+supplies[t+1]:\n",
    "                    t=i\n",
    "            supplies[t]+=supplies[t+1]\n",
    "            supplies.pop(t+1)\n",
    "        return supplies\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        n = len(supplies) // 2\n",
    "        while len(supplies) > n:\n",
    "            res = -1\n",
    "            min_ = float('inf')\n",
    "            for i in range(len(supplies) - 1):\n",
    "                x = supplies[i] + supplies[i + 1]\n",
    "                if x < min_:\n",
    "                    min_ = x\n",
    "                    res = i\n",
    "            supplies[res] = min_\n",
    "            supplies.pop(res+1)\n",
    "        return supplies        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        m = len(supplies) // 2\n",
    "        while len(supplies) > m:\n",
    "            idx = 1\n",
    "            for i in range(1, len(supplies)):\n",
    "                if supplies[i] + supplies[i-1] < supplies[idx] + supplies[idx-1]:\n",
    "                    idx = i \n",
    "            supplies[idx-1] += supplies[idx]\n",
    "            supplies.pop(idx)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        target_len = len(supplies) // 2\n",
    "        while len(supplies) > target_len:\n",
    "            min_val, min_idx = inf, 0\n",
    "            for i in range(len(supplies)-1):\n",
    "                cur_sum = supplies[i] + supplies[i+1]\n",
    "                if cur_sum < min_val:\n",
    "                    min_val = cur_sum\n",
    "                    min_idx = i \n",
    "            supplies = supplies[:min_idx] + [min_val] + supplies[min_idx+2:]\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, a: List[int]) -> List[int]:\n",
    "        m = len(a) // 2\n",
    "        while len(a) > m:\n",
    "            idx = 1\n",
    "            for i in range(1, len(a)):\n",
    "                if a[i - 1] + a[i] < a[idx - 1] + a[idx]:\n",
    "                    idx = i\n",
    "            a[idx - 1] += a[idx]\n",
    "            a.pop(idx)\n",
    "        return a\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        lenth=len(supplies)//2\n",
    "        while len(supplies)>lenth:\n",
    "            list1=[]\n",
    "            for i in range(len(supplies)-1):\n",
    "                list1.append(supplies[i+1]+supplies[i])\n",
    "            minn=list1.index(min(list1))\n",
    "            supplies[minn]=supplies[minn]+supplies[minn+1]\n",
    "            supplies.pop(minn+1)\n",
    "        return supplies\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        l = len(supplies)//2\n",
    "        while True:\n",
    "            new = []\n",
    "            for i in range(0,len(supplies)-1):\n",
    "                a = supplies[i] + supplies[i+1]\n",
    "                new.append(a)\n",
    "            b = min(new)\n",
    "            index = new.index(b)\n",
    "            supplies[index] = b\n",
    "            del supplies[index+1]\n",
    "            if len(supplies) == l:\n",
    "                break\n",
    "        return supplies\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        if len(supplies) == 2:\n",
    "            return [sum(supplies)]\n",
    "        for _ in range((len(supplies) + 1) // 2):\n",
    "            min_rst = [300000, 1]\n",
    "            for i in range(1, len(supplies)):\n",
    "                if supplies[i] + supplies[i - 1] < min_rst[0]:\n",
    "                    min_rst[0] = supplies[i] + supplies[i - 1]\n",
    "                    min_rst[1] = i\n",
    "            supplies[min_rst[1]] = min_rst[0]\n",
    "            del supplies[min_rst[1] - 1]\n",
    "        return supplies\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, a: List[int]) -> List[int]:\n",
    "        m = len(a) // 2\n",
    "        while len(a) > m:\n",
    "            idx = 1\n",
    "            for i in range(1, len(a)):\n",
    "                if a[i - 1] + a[i] < a[idx - 1] + a[idx]:\n",
    "                    idx = i\n",
    "            a[idx - 1] += a[idx]\n",
    "            a.pop(idx)\n",
    "        return a\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, a: List[int]) -> List[int]:\n",
    "        m = len(a) // 2\n",
    "        while len(a) > m:\n",
    "            idx = 1\n",
    "            for i in range(1, len(a)):\n",
    "                if a[i - 1] + a[i] < a[idx - 1] + a[idx]:\n",
    "                    idx = i\n",
    "            a[idx - 1] += a[idx]\n",
    "            a.pop(idx)\n",
    "        return a\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        supplies_len = len(supplies)//2\n",
    "        while len(supplies) != supplies_len:\n",
    "            result = supplies[0]+supplies[1]\n",
    "            a = None\n",
    "            b = None\n",
    "            for i in range(1,len(supplies)-1):\n",
    "                if supplies[i]+supplies[i+1] < result:\n",
    "                    result = supplies[i]+supplies[i+1]\n",
    "                    a = i\n",
    "                    b = i+1\n",
    "                    continue\n",
    "            if a==None and b==None:\n",
    "                a = 0\n",
    "                b = 1\n",
    "            del supplies[b]\n",
    "            del supplies[a]\n",
    "            supplies.insert(a,result)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        target = len(supplies) // 2\n",
    "        while len(supplies) > target:\n",
    "            ans = sum(supplies[: 2])\n",
    "            begin = 0\n",
    "            \n",
    "            for i in range(2, len(supplies)):\n",
    "                new = supplies[i - 1] + supplies[i]\n",
    "                if new < ans:\n",
    "                    ans = new\n",
    "                    begin = i - 1\n",
    "            supplies.pop(begin)\n",
    "            supplies.pop(begin)\n",
    "            supplies.insert(begin, ans)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        init_n = len(supplies)\n",
    "        while(len(supplies)>init_n/2):\n",
    "            min_index = 0\n",
    "            min_sum = max(supplies)*2\n",
    "            for i in range(len(supplies)-1):\n",
    "                temp = supplies[i]+supplies[i+1]\n",
    "                min_index = i if temp<min_sum else min_index\n",
    "                min_sum = temp if temp<min_sum else min_sum\n",
    "            supplies[min_index+1] = min_sum\n",
    "            supplies.pop(min_index)\n",
    "            # print(supplies)\n",
    "        return supplies\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, a: List[int]) -> List[int]:\n",
    "        m = len(a) // 2\n",
    "        while len(a) > m:\n",
    "            idx = 1\n",
    "            for i in range(1, len(a)):\n",
    "                if a[i - 1] + a[i] < a[idx - 1] + a[idx]:\n",
    "                    idx = i\n",
    "            a[idx - 1] += a[idx]\n",
    "            a.pop(idx)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        a = supplies\n",
    "        k = len(a) // 2 if len(a) % 2 == 0 else len(a) // 2 + 1\n",
    "        for i in range(k):\n",
    "            min = 100000000\n",
    "            minIndex = -1\n",
    "            for j in range(len(a) - 1):\n",
    "                if(a[j] + a[j + 1] < min):\n",
    "                    min = a[j] + a[j+1]\n",
    "                    minIndex = j\n",
    "            del a[minIndex]\n",
    "            a[minIndex] = min\n",
    "        return a\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        length = len(supplies)     # 表示原先有几辆车 \n",
    "        if length < 2:\n",
    "            return supplies\n",
    "\n",
    "        while len(supplies) > length // 2:\n",
    "            # print(supplies[0:2])\n",
    "            \n",
    "            sup_min = sum(supplies[0:2])\n",
    "            stage = 0\n",
    "            for i in range(1,len(supplies)-1):\n",
    "                if sum(supplies[i:i+2]) < sup_min:\n",
    "                    sup_min = sum(supplies[i:i+2])\n",
    "                    stage = i\n",
    "                    # print(stage)\n",
    "            supplies[stage] = sup_min\n",
    "            supplies.pop(stage+1)\n",
    "            # print(supplies)\n",
    "            # print(len(supplies))\n",
    "        return supplies\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        size = len(supplies)\n",
    "        size2 = size // 2\n",
    "        while size > size2:\n",
    "            size = self.mergeMin(supplies, size)\n",
    "        result = [supplies[i] for i in range(size)]\n",
    "        return result\n",
    "\n",
    "    def mergeMin(self, data: List[int], size: int) -> int:\n",
    "        minVal = data[0] + data[1]\n",
    "        minIndex = 0\n",
    "        for i in range(size - 1):\n",
    "            if data[i] + data[i + 1] < minVal:\n",
    "                minVal = data[i] + data[i + 1]\n",
    "                minIndex = i\n",
    "        i = minIndex\n",
    "        j = minIndex + 1\n",
    "        data[i] += data[j]\n",
    "\n",
    "        for i in range(j, size - 1):\n",
    "            data[i] = data[i + 1]\n",
    "        size -= 1\n",
    "        return size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        half = len(supplies)//2\n",
    "        while len(supplies)>half:\n",
    "            comblst = [supplies[i]+supplies[i+1] for i in range(len(supplies)-1)]\n",
    "            minsum = min(comblst)\n",
    "            idx = comblst.index(minsum)\n",
    "            supplies[idx] = minsum\n",
    "            supplies.pop(idx+1)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        n = len(supplies) // 2\n",
    "        while len(supplies) > n:\n",
    "            res = -1\n",
    "            diff = []\n",
    "            min_ = float('inf')\n",
    "            for i in range(len(supplies) - 1):\n",
    "                x = supplies[i] + supplies[i + 1]\n",
    "                if x < min_:\n",
    "                    min_ = x\n",
    "                    res = i\n",
    "            supplies = supplies[:res] + [min_] + supplies[res + 2:]\n",
    "        return supplies        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        target_len = len(supplies) // 2\n",
    "        while len(supplies) > target_len:\n",
    "            min_idx = 0 \n",
    "            min_v = float(inf)\n",
    "            \n",
    "            for i in range(len(supplies)-1):\n",
    "                if supplies[i] + supplies[i+1] < min_v:\n",
    "                    min_idx = i \n",
    "                    min_v = supplies[i] + supplies[i+1]\n",
    "            supplies[min_idx] = supplies[min_idx] + supplies[min_idx+1]\n",
    "            supplies.pop(min_idx+1)\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        m = len(supplies) // 2\n",
    "        while len(supplies) > m:\n",
    "            idx = 1\n",
    "            for i in range(1, len(supplies)):\n",
    "                if supplies[i - 1] + supplies[i] < supplies[idx - 1] + supplies[idx]:\n",
    "                    idx = i\n",
    "            supplies[idx - 1] += supplies[idx]\n",
    "            supplies.pop(idx)\n",
    "        return supplies\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        l = len(supplies)\n",
    "        t = l // 2\n",
    "        while len(supplies) > t:\n",
    "            m = [0, 1]\n",
    "            mv = supplies[0] + supplies[1]\n",
    "            for i in range(1, len(supplies)):\n",
    "                nv = supplies[i] + supplies[i - 1]\n",
    "                if nv < mv:\n",
    "                    m = [i - 1, i]\n",
    "                    mv = nv\n",
    "            supplies = supplies[:m[0]] + [mv] + supplies[m[1] + 1 :]\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        target_length = len(supplies) // 2\n",
    "\n",
    "        while len(supplies) > target_length:\n",
    "            min_sum = float('inf')\n",
    "            min_idx = -1\n",
    "            # 找到物资之和最小的相邻马车\n",
    "            for i in range(len(supplies)-1):\n",
    "                if supplies[i] + supplies[i+1] < min_sum:\n",
    "                    min_sum = supplies[i] + supplies[i+1]\n",
    "                    min_idx = i\n",
    "            # 整合两辆马车\n",
    "            supplies[min_idx] = min_sum\n",
    "            del supplies[min_idx+1]\n",
    "\n",
    "        return supplies\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        should_length = len(supplies) // 2\n",
    "        supply = [supplies[i] + supplies[i + 1] for i in range(len(supplies) - 1)]\n",
    "        while len(supplies) != should_length:\n",
    "            min_index, min_value = min(enumerate(supply), key=lambda x: x[1])\n",
    "            supplies[min_index] = min_value\n",
    "            supplies.pop(min_index + 1)\n",
    "            supply = [supplies[i] + supplies[i + 1] for i in range(len(supplies) - 1)]\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        times=len(supplies)-len(supplies)//2\n",
    "        st=supplies\n",
    "        for i in range(times):\n",
    "            m,n=0,1\n",
    "            min=st[0]+st[1]\n",
    "            for j in range(1,len(supplies)-1):\n",
    "                if min>st[j]+st[j+1]:\n",
    "                    m,n=j,j+1\n",
    "                    min=st[j]+st[j+1]\n",
    "            # 让索引小的值等于合并后的值\n",
    "            st[m]=min\n",
    "            del st[n]\n",
    "        print(st)\n",
    "        return st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        # > 输入：`supplies = [7,3,6,1,8]`\n",
    "        # >\n",
    "        # > 输出：`[10,15]`\n",
    "        # >\n",
    "        # > 解释：\n",
    "        # > 第 1 次合并，符合条件的两辆马车为 6,1，合并后的车队为 [7,3,7,8]；\n",
    "        # > 第 2 次合并，符合条件的两辆马车为 (7,3) 和 (3,7)，取编号最小的 (7,3)，合并后的车队为 [10,7,8]；\n",
    "        # > 第 3 次合并，符合条件的两辆马车为 7,8，合并后的车队为 [10,15]；\n",
    "        # > 返回 `[10,15]`\n",
    "        n = len(supplies) // 2\n",
    "        while len(supplies) > n:\n",
    "            min_pos = 0\n",
    "            s = sum(supplies[:2])\n",
    "            i = 1\n",
    "            while i < len(supplies) - 1:\n",
    "                cur_s = sum(supplies[i:i + 2])\n",
    "                if cur_s < s:\n",
    "                    min_pos = i\n",
    "                    s = cur_s\n",
    "                i += 1\n",
    "            supplies = supplies[:min_pos] + [sum(supplies[min_pos:min_pos + 2])] + supplies[min_pos + 2:]\n",
    "        return supplies\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        length = int(len(supplies) / 2)\n",
    "        while len(supplies) > length:\n",
    "            minsum = supplies[0] + supplies[1]\n",
    "            order = 0\n",
    "            for i in range(1, len(supplies) - 1):\n",
    "                sum = supplies[i] + supplies[i + 1]\n",
    "                if sum < minsum:\n",
    "                    minsum = sum\n",
    "                    order = i\n",
    "            tmp = supplies[:order]\n",
    "            tmp.append((supplies[order] + supplies[order + 1]))\n",
    "            supplies = tmp + supplies[order + 2:]\n",
    "        return supplies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def supplyWagon(self, supplies: List[int]) -> List[int]:\n",
    "        supplies_len = len(supplies)//2\n",
    "        while len(supplies) != supplies_len:\n",
    "            result = supplies[0]+supplies[1]\n",
    "            a = None\n",
    "            b = None\n",
    "            for i in range(1,len(supplies)-1):\n",
    "                if supplies[i]+supplies[i+1] < result:\n",
    "                    result = supplies[i]+supplies[i+1]\n",
    "                    a = i\n",
    "                    b = i+1\n",
    "                    continue\n",
    "            if a==None and b==None:\n",
    "                a = 0\n",
    "                b = 1\n",
    "            del supplies[b]\n",
    "            del supplies[a]\n",
    "            supplies.insert(a,result)\n",
    "        return supplies"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
